package com.zhj.interview;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author zhj
 * @create 2023-11-28-14:03
 */
public class Test23 {
    /**
     * 实现LRU缓存淘汰策略
     * LRU：最近做少使用
     * 实现方式一：继承LinkedHashMap
     * 实现方式二：基于LinkedList+HashMap
     */
    public static void main(String[] args) {
        // Map<Integer, Integer> cache = new LRUCache1<>(2);
        LRUCache2 cache = new LRUCache2<>(2);
        cache.put(1,1);
        cache.put(2,2);
        cache.put(3,3);
        cache.get(2);
        cache.put(4,4);
    }

    static class LRUCache1<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        public LRUCache1(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }

        /**
         *  默认LinkedHashMap不会删除元素，重写removeEldestEntry方法是其返回true
         *  void afterNodeInsertion(boolean evict) { // possibly remove eldest
         *      LinkedHashMap.Entry<K,V> first;
         *      if (evict && (first = head) != null && removeEldestEntry(first)) {
         *          K key = first.key;
         *          removeNode(hash(key), key, null, false, true);
         *      }
         *  }
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
    }

    static class LRUCache2<K, V> {

        private final int capacity;

        private final Map<K, V> cache;

        private final LinkedList<K> keyList;

        public LRUCache2(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>(capacity);
            this.keyList = new LinkedList<>();
        }

        public synchronized void put(K key, V value) {
            if (cache.containsKey(key)) {
                keyList.remove(key);
            }
            while (cache.size() >= capacity) {
                K oldestKey = keyList.removeFirst();
                cache.remove(oldestKey);
            }
            cache.put(key, value);
            keyList.addLast(key);
        }

        public synchronized V get(K key) {
            if (cache.containsKey(key)) {
                keyList.remove(key);
                keyList.addLast(key);
                return cache.get(key);
            }
            return null;
        }

    }
}
